import java.util.*;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-46-全排列
 * @date 2025/4/28 10:17
 */
public class Solution46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();

        // 返回一个ArrayList<Integer>,不可变化容量
        List<Integer> path = Arrays.asList(new Integer[nums.length]);
        boolean[] onPath = new boolean[nums.length];
        dfs(0, nums, path, onPath, ans);

        return ans;
    }

    private void dfs(int i, int[] nums, List<Integer> path, boolean[] onPath, List<List<Integer>> ans) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            if (!onPath[j]) {
                path.set(i, nums[j]);
                onPath[j] = true;
                dfs(i + 1, nums, path, onPath, ans);
                // 保护现场,以便递归返回到上一层的时候可以再次遍历
                onPath[j] = false;
            }
        }
    }

}
